#include <cstdlib>
#include <cassert>

#include <iostream>
#include <vector>
#include <algorithm>

#include "common.h"
#include <iostream>

using std::vector;

// putative_exons have to sorted according to their starting point.
// Returns direction vector
const vector<const exon*> GetOptimalChainDirections(const vector<exon>& exons) {
	assert(std::is_sorted(exons.begin(), exons.end(), [](const exon e1, const exon e2) -> bool {
		return e1.l < e2.l;
	}));
	// conservative size estimate
	vector<int> pts(exons.back().r);
	// points to exon from which we jumped to this position or nullptr if we don't jump
	// to this position
	vector<const exon*> prev(exons.back().r, nullptr);
	int last_pos = 0;
	std::for_each(exons.begin(), exons.end(), [&pts, &last_pos, &prev] (const exon& e) {

		// update all points for positions before this one
		for (int i = last_pos + 1; i <= e.l; i++) {
			if (pts[i - 1] >= pts[i]) {
				pts[i] = pts[i - 1];
				prev[i] = nullptr; // don't jump here
			}
		}
		last_pos = e.l;
		if (pts.size() <= (size_t)e.r) {
			pts.resize(e.r + 1);
		}
		if (prev.size() <= (size_t)e.r) {
			prev.resize(e.r + 1);
		}
		if (pts[e.r] < pts[e.l] + e.w) {
			prev[e.r] = &e;
			pts[e.r] = pts[e.l] + e.w;
		}
	});
	return prev;
}

// Given the exon vector and the previous jumps, we return the chain of nonoverlapping exons
// that maximizes the weight
const vector<exon> GetExonsFromChain(const vector<exon>& exons, const vector<const exon*>& prev) {
	vector<exon> result;
	int pos = prev.size() - 1;
	while (pos >= 0 && prev[pos] == nullptr) pos--;
	while (pos >= 0) {
		exon e = *prev[pos];
		result.push_back(e);
		pos = e.l;
		while (pos >= 0 && prev[pos] == nullptr) pos--;
	}
	// we want to get the chain ordered from smallest to largest not reversed
	std::reverse(result.begin(), result.end());
	return result;
}

int main(int argc, char **argv) {
	const vector<exon> exons = {
			{0, 3, 4},
			{4, 7, 4},
			{7, 9, 3}
	};
	const vector<const exon *> prev = GetOptimalChainDirections(exons);
	const vector<exon> result = GetExonsFromChain(exons, prev);
	std::for_each(result.begin(), result.end(), [](const exon &e) {
		std::cout << e << std::endl;
	});
	return EXIT_SUCCESS;
}
